//实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：x = 2.00000, n = 10
//输出：1024.00000
// 
//
// 示例 2： 
//
// 
//输入：x = 2.10000, n = 3
//输出：9.26100 
//
// 示例 3： 
//
// 
//输入：x = 2.00000, n = -2
//输出：0.25000
//解释：2-2 = 1/22 = 1/4 = 0.25 
//
// 
//
// 提示： 
//
// 
// -100.0 < x < 100.0 
// -231 <= n <= 231-1 
// -104 <= xn <= 104 
// 
//
// 
//
// 注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/ 
// Related Topics 递归 数学 
// 👍 184 👎 0


package leetcode.editor.cn1;

//Java：数值的整数次方

/**
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
 * <p>
 * 输入：x = 2.00000, n = 10
 * 输出：1024.00000
 *
 * 二分推导
 */
public class ShuZhiDeZhengShuCiFangLcof_1028 {
    public static void main(String[] args) {
        Solution solution = new ShuZhiDeZhengShuCiFangLcof_1028().new Solution();
        // TO TEST
        System.out.println(solution.myPow(2.1, 3));
        System.out.println(solution.myPow(2, 10));
        System.out.println(solution.myPow(2, -2));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double myPow(double x, int n) {
            // 如果x = 0，并且n < 0毫无意义
            if (x == 0 && n < 0)
                return -1;
            // 如果n < 0，取n的绝对值
            // Java 代码中 int32 变量 n \in [-2147483648, 2147483647]n∈[−2147483648,2147483647] ，因此当 n = -2147483648n=−2147483648 时执行 n = -nn=−n 会因越界而赋值出错。解决方法是先将 nn 存入 long 变量 bb ，后面用 bb 操作即可。
            long b = n;
            long k = n;
            if (b < 0)
                b = Math.abs(b);

            // 计算x的n次方
            double res = powDif(x, b);
            if (k < 0)
                return 1 / res;
            return res;
        }

        public double powDif(double x, long b) {
            if (b == 0)
                return 1;
            if (b == 1)
                return x;
            double res = 1;
            // 循环解决递归问题
            // 递归方法会导致栈溢出
            while (b > 0) {
                // 如果b是奇数，把多出来的数字赋值给res
                if ((b & 1) == 1)
                    res = res * x;
                x = x * x;
                // 右移1位
                b = b >> 1;
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
